home *** CD-ROM | disk | FTP | other *** search
/ Apple WWDC 1996 / WWDC96_1996 (CD).toast / Technology Materials / MacApp Release 10 / MacApp Release 10 - HD Ready / Libraries / Core / Includes / UDynamicArray.h < prev    next >
Encoding:
Text File  |  1996-04-03  |  10.8 KB  |  291 lines  |  [TEXT/MPS ]
  1. // UDynamicArray.h
  2. // Copyright © 1984-96 by Apple Computer, Inc. All rights reserved.
  3.  
  4. #ifndef __UDYNAMICARRAY__
  5. #define __UDYNAMICARRAY__
  6.  
  7. // MacApp
  8.  
  9. #ifndef __UOBJECT__
  10. #include "UObject.h"
  11. #endif
  12.  
  13. // ANSI
  14.  
  15. #ifndef __STDDEF__
  16. #include <stddef.h>
  17. #endif
  18.  
  19.  
  20. //----------------------------------------------------------------------------------------
  21. // Forward and external class declarations
  22. //----------------------------------------------------------------------------------------
  23.  
  24. class CArrayIterator;
  25.  
  26.  
  27. const short kAllocationIncrement = 6;            // Initial Allocation increment. Six
  28.                                                 // elements of slop shouldn't break
  29.                                                 // anybody and provides a _nice_ cushion
  30.                                                 // from the memory manager.
  31.  
  32.  
  33. //----------------------------------------------------------------------------------------
  34. // Constants for TDynamicArray::CompareElements and TSortedxxx::Compare
  35. //----------------------------------------------------------------------------------------
  36. enum {
  37.     kItem1LessThanItem2 = -1,
  38.     kItem1EqualItem2 = 0,
  39.     kItem1GreaterThanItem2 = 1
  40. };
  41.  
  42.  
  43. //----------------------------------------------------------------------------------------
  44. // Constants for TSortedList::Search. The criteria is considered to be item 2
  45. //----------------------------------------------------------------------------------------
  46.  
  47. enum {
  48.     kItemGreaterThanCriteria = kItem1LessThanItem2,
  49.     kItemEqualCriteria = kItem1EqualItem2,
  50.     kItemLessThanCriteria = kItem1GreaterThanItem2
  51. };
  52.  
  53. typedef short CompareResult;
  54.     // Negative, zero, and positive results are all meaningful even though we have the
  55.     // nice constants above.
  56.  
  57.  
  58. //----------------------------------------------------------------------------------------
  59. // procedure typedefs for parameters
  60. //----------------------------------------------------------------------------------------
  61.  
  62. typedef CompareResult (*CompareIndexType)(ArrayIndex anItem, void* yourDataPtr);
  63.  
  64. typedef CompareResult(* CompareElementsType)(void* element1,
  65.                                             void* Element2,
  66.                                             void* yourDataPtr);
  67.  
  68.  
  69. //----------------------------------------------------------------------------------------
  70. // TDynamicArray
  71. //----------------------------------------------------------------------------------------
  72.  
  73. class TDynamicArray : public TObject
  74. {
  75.     MA_DECLARE_CLASS;
  76.     
  77. public:
  78.     //------------------------------------------------------------------------------------
  79.     // Creation/ Destruction Methods
  80.     //------------------------------------------------------------------------------------
  81.  
  82.     TDynamicArray();
  83.         // Constructor
  84.     virtual ~TDynamicArray();
  85.         // Destructor
  86.         
  87.     void IDynamicArray(ArrayIndex initialSize,
  88.                                       short elementSize);
  89.         // Initialize a new array with initialSize elements, Always call it once before
  90.         // calling any other method. Never call it twice.
  91.  
  92.     virtual TObject* Clone();
  93.  
  94.     virtual void Free();
  95.         // If enumeration of the array is in process, delete all the array elements, mark
  96.         // the fFreeRequested flag for testing at completion of the enumeration and
  97.         // return. Otherwise really free the array. Gee, wouldn't automatic storage
  98.         // management be great!
  99.  
  100.     //------------------------------------------------------------------------------------
  101.     // Stream I/O protocol support.
  102.     //------------------------------------------------------------------------------------
  103.  
  104.     virtual void ReadFrom(TStream* aStream);
  105.     
  106.     virtual void WriteTo(TStream* aStream);
  107.  
  108.  
  109.     //------------------------------------------------------------------------------------
  110.     // Array manipulation primitives
  111.     //------------------------------------------------------------------------------------
  112.  
  113.     void* operator[](ArrayIndex index) const;
  114.         // Returns a pointer to the index-th element in the array.
  115.         // the index is "zero" based.
  116.         
  117.     void* ComputeAddress(ArrayIndex index) const;
  118.         // Returns a pointer to of the index-th element in the array.
  119.         // the index is "one" based.
  120.  
  121.     ArrayIndex GetSize() const
  122.     { return fSize; }
  123.         // Returns the ACTUAL number of elements in the array.
  124.  
  125.     void SetArraySize(ArrayIndex theSize);
  126.         // Sets the array allocation to handle up to theSize elements
  127.  
  128.     void InsertElementsBefore(ArrayIndex index,
  129.                                          const void* ElementPtr,
  130.                                          ArrayIndex count);
  131.         // Insert Elements before the indicated Element. The index of the new element will
  132.         // be index. If index = 1 this inserts at the start of the array. If index = fSize
  133.         // + 1 this inserts at the end of the array. Signals Failure if unable to change
  134.         // the size of the array. !!! NOTE MULTIPLE ( >1 ) element moves for non-power of
  135.         // 2 element sizes are NOT yet supported!
  136.  
  137.     void ReplaceElementsAt(ArrayIndex index,
  138.                                       const void* ElementPtr,
  139.                                       ArrayIndex count);
  140.         // Replaces the Elements at the indicated index. !!! NOTE MULTIPLE ( >1 ) element
  141.         // moves for non-power of 2 element sizes are NOT yet supported!
  142.  
  143.     void DeleteElementsAt(ArrayIndex index,
  144.                                          ArrayIndex count);
  145.         // Deletes the Element at the indicated index. Compresses the array !!! NOTE
  146.         // MULTIPLE ( >1 ) element moves for non-power of 2 element sizes are NOT yet
  147.         // supported!
  148.  
  149.     void GetElementsAt(ArrayIndex index,
  150.                                       void* ElementPtr,
  151.                                       ArrayIndex count);
  152.         // copies count elements to the location specified by ptr. !!! NOTE MULTIPLE ( >1
  153.         // ) element moves for non-power of 2 element sizes are NOT yet supported!
  154.  
  155.     void DeleteAll();
  156.         // Delete every element from the list Leave fSize at 0.
  157.         
  158.     //------------------------------------------------------------------------------------
  159.     // Misc. functions
  160.     //------------------------------------------------------------------------------------
  161.  
  162.     inline Boolean IsEmpty() const
  163.     { return fSize == kEmptyIndex; }
  164.         // Test if this array is empty or not.
  165.  
  166.     void Merge(TDynamicArray* aDynamicArray);
  167.         // merges aDynamicArray with itself. leaves aDynamicArray unchanged. !!! NOTE
  168.         // MULTIPLE ( >1 ) element moves for non-power of 2 element sizes are NOT yet
  169.         // supported!
  170.  
  171.     //------------------------------------------------------------------------------------
  172.     // Public Sorting access
  173.     //------------------------------------------------------------------------------------
  174.     virtual CompareResult CompareElements(void* Element1, void* Element2);
  175.         // Returns the sort order between elements of the array. Default considers
  176.         // all elements equivalent.
  177.  
  178.     virtual void Sort();
  179.         // Sorts the list usingthe Compare and SortBy methods.
  180.  
  181.     virtual void SortElementsBy(CompareElementsType CompareItems, void* yourDataPtr);
  182.         // Sorts the list using the supplied CompareItems function.
  183.  
  184.     //------------------------------------------------------------------------------------
  185.     // Sorting
  186.     //------------------------------------------------------------------------------------
  187. protected:
  188.     void* GetSwapBuffer();
  189.         // Returns a buffer to use in element exchanges
  190.  
  191.     void ReleaseSwapBuffer(void* swapBuffer);
  192.         // Releases a buffer returned by GetSwapBuffer
  193.  
  194.     void SwapElements(void* element1, void* element2, void* swapBuffer);
  195.         // Swaps two elements using the supplied swapbuffer
  196.  
  197.     void QuickSort(ArrayIndex beginIndex,
  198.                                   ArrayIndex endIndex,
  199.                                   CompareElementsType CompareItems,
  200.                                   void* yourDataPtr,
  201.                                   void* swapBuffer);
  202.         // Uses QuickSort Algorithm, adapted from:
  203.         //    Cormen, Leiserson, and Rivest, _Introductions_To_Algorithms_, pp 153-167.
  204.  
  205.     ArrayIndex QSPartition(ArrayIndex beginIndex,
  206.                                         ArrayIndex endIndex,
  207.                                         CompareElementsType CompareItems,
  208.                                         void* yourDataPtr,
  209.                                         void* swapBuffer);
  210.         // Called by RandomPartition. Partitions the array A[beginIndex..endIndex] in place
  211.  
  212.     ArrayIndex QSRandomPartition(ArrayIndex beginIndex,
  213.                                         ArrayIndex endIndex,
  214.                                         CompareElementsType CompareItems,
  215.                                         void* yourDataPtr,
  216.                                         void* swapBuffer);
  217.         // Called by QuickSort. Partitions the array A[beginIndex..endIndex] in place
  218.  
  219.     //------------------------------------------------------------------------------------
  220.     // data members
  221.     //------------------------------------------------------------------------------------
  222.  
  223. public:
  224.     Ptr fArraySpace;                            // space for actually storing the elements
  225.                                                 // of this TDynamicArray.
  226.         
  227.     CArrayIterator* fIteratorPtr;                // pointer to the Iterators in use
  228.  
  229.     ArrayIndex fSize;                            // number of elements ACTUALLY in the
  230.                                                 // array, from 0 to the limit of memory
  231.  
  232.     ArrayIndex fAllocationIncrement;            // Number of elements by which to increase
  233.                                                 // of decrease the allocated size of the
  234.                                                 // array when it needs to grow or shrink.
  235.                                                 // Thus reducing memory manager
  236.                                                 // aggravation.
  237.  
  238.     ArrayIndex fAllocatedSize;                    // Number of elements for which storage is
  239.                                                 // ALLOCATED
  240.  
  241.     unsigned short fElementSize;                // Size in bytes of an element. MUST be a
  242.                                                 // power of 2 ie. 1, 2, 4, 8, 16, etc.
  243.  
  244.     unsigned short fElementSizeShift;            // the power of 2 for the element size.
  245.                                                 // Will be used to avoid DIV and MUL
  246.  
  247.     Boolean fFreeRequested;                        // True if the Free method was called but
  248.                                                 // couldn't be honored because enumeration
  249.                                                 // was in process. Checked at end of
  250.                                                 // enumeration and Free is called if true
  251. };
  252.  
  253.  
  254. //----------------------------------------------------------------------------------------
  255. // TSortedDynamicArray: A TDynamicArray with ordering.
  256. //----------------------------------------------------------------------------------------
  257.  
  258. class TSortedDynamicArray : public TDynamicArray
  259. {
  260.     MA_DECLARE_CLASS;
  261.     
  262. public:
  263.  
  264.     inline TSortedDynamicArray()
  265.     { }
  266.         // Empty constructor
  267.  
  268.     virtual ~TSortedDynamicArray();
  269.         // Destructor
  270.         
  271.     inline void ISortedDynamicArray(ArrayIndex initialSize, short elementSize)
  272.     { IDynamicArray(initialSize, elementSize); }
  273.         // Initialize a new array with initialSize elements, Always call it once before
  274.         // calling any other method. Never call it twice.
  275.  
  276.     virtual void InsertElementInOrder(void* ElementPtr);
  277.         // Insert an element in its correct position according to the ordering defined by
  278.         // the Compare method
  279.  
  280.     virtual Boolean DoSearchElement(CompareIndexType TestItem,
  281.                                            void* yourDataPtr,
  282.                                            ArrayIndex& index);
  283.         // !!! Adapted from TSortedList. Performs a binary search for an element for which
  284.         // TestItem returns true. "index" returns the position of a found item, or where
  285.         // it should be inserted if not found
  286.  
  287. };
  288.  
  289.  
  290. #endif
  291.